package org.example.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 93. 复原 IP 地址
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，
 * 这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
 */
public class Code93 {
    List<String> res=new ArrayList<>();
    StringBuilder str=new StringBuilder();
    public List<String> restoreIpAddresses(String s) {
        res.clear();
        backtracking(s,0,0);
        return res;
    }

    private void backtracking(String s, int startIndex,int point) {
        // 如果已经有4个段了，检查是否遍历完整个字符串
        if (point == 4) {
            if (startIndex == s.length()) {
                // 删除最后一个点并添加结果
                res.add(str.substring(0, str.length() - 1));
            }
            return;
        }
        // 如果已经遍历完字符串但段数不足4，直接返回
        if (startIndex == s.length()) {
            return;
        }
        for(int i=startIndex;i<s.length() && i < startIndex + 3;i++){
            // 检查当前子串是否为有效IP段
            if (isVal(s, startIndex, i)) {
                // 记录当前str长度，用于回溯
                int originLength = str.length();

                // 添加当前段和点
                str.append(s.substring(startIndex, i + 1)).append(".");

                // 递归处理下一个段
                backtracking(s, i + 1, point + 1);

                // 回溯，恢复str到之前的状态
                str.setLength(originLength);
            }
        }
    }

    private boolean isVal(String s, int startIndex, int end) {
        // 检查子串长度
        if (end - startIndex + 1 > 3) {
            return false;
        }

        // 检查是否含有前导0
        if (s.charAt(startIndex) == '0' && startIndex != end) {
            return false;
        }

        // 解析数字并检查范围
        int num = 0;
        for (int i = startIndex; i <= end; i++) {
            // 检查是否为数字字符
            if (s.charAt(i) < '0' || s.charAt(i) > '9') {
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
        }

        // 检查数值范围
        return num >= 0 && num <= 255;
    }
    public static void main(String[] args) {
        Code93 solution = new Code93();

        // 测试用例1
        String s1 = "1111";
        List<String> result1 = solution.restoreIpAddresses(s1);
        System.out.println("输入: \"" + s1 + "\"");
        System.out.println("输出: " + result1);
        System.out.println();

        // 测试用例2
        String s2 = "101023";
        List<String> result2 = solution.restoreIpAddresses(s2);
        System.out.println("输入: \"" + s2 + "\"");
        System.out.println("输出: " + result2);
        System.out.println();

        // 测试用例3
        String s3 = "1111";
        List<String> result3 = solution.restoreIpAddresses(s3);
        System.out.println("输入: \"" + s3 + "\"");
        System.out.println("输出: " + result3);
        System.out.println();

        // 测试用例4
        String s4 = "0000";
        List<String> result4 = solution.restoreIpAddresses(s4);
        System.out.println("输入: \"" + s4 + "\"");
        System.out.println("输出: " + result4);
        System.out.println();

        // 测试用例5
        String s5 = "101023";
        List<String> result5 = solution.restoreIpAddresses(s5);
        System.out.println("输入: \"" + s5 + "\"");
        System.out.println("输出: " + result5);
    }
}
